Arithmetic in finite fields is used extensively in applications such as coding-theory and cryptography. Cryptographic systems, in particular, make extensive use of modular arithmetic. Making calculations modulo n is like performing normal arithmetic in that it is commutative, associative and distributive. Modular arithmetic is also easier to work with since the ranges of intermediate values and results for addition, multiplication and subtraction are restricted. This is of particular importance when the computations implemented on a processor which has limited register length and speed.
In modular arithmetic, the set of integers modulo m is denoted F.sub.m ={0,1,2, . . . , m-1}. When m is a prime number p, then the set of integers modulo p, F.sub.p, forms a finite field in which we can perform operations of addition, multiplication and subtraction. Furthermore, if F.sub.p ={0,1,2, . . . p-1} and C.sub.i is an element of F.sub.p, then the set of polynomials in x with coefficients from F.sub.p is F.sub.p [x]={ Cnx"+ . . . +Co.vertline.Ci.di-elect cons.F.sub.p,n.gtoreq.0}.
As defined above, where the arithmetic is performed modulo a prime integer p, cryptographers may also use arithmetic modulo an irreducible polynomial f(x) of degree n whose coefficients are integers modulo q, where q is prime. These fields are designated symbolically by F(q.sup.n). Thus all arithmetic is done modulo some f(x) which is an irreducible polynomial of degree n and in which the coefficients of the polynomial are elements of a finite field. If q is equal to 2, then computation in F(2.sup.n) can be quickly implemented in hardware with linear feedback shift registers. For that reason, computation of a F(2.sup.n) is often quicker than computation over F(p).
The values of n which make a feasible cryptographic system tend to be relatively large. Finite fields used in cryptography are typically chosen from those with characteristic two, since these lend themselves to binary hardware and processors. A further specialization of the field of characteristic two are those having an optimal normal basis, either of type I or II. Bases of type I which are optimal normal bases have the characteristic that the coefficients of a polynomial expressed in terms of a polynomial basis are the permuted coefficients of the polynomial expressed in terms of a normal basis.
A finite field may be constructed from a generating element .alpha. and is composed of a vector space of the powers of .alpha. modulo the irreducible polynomial f(x) of degree n. For example F2.sup.3 has the following elements: 0, 1, x, x+1, x.sup.2, x.sup.2 +1, x, x.sup.2 +x, x.sup.2 +x+1. The component powers of .alpha. can then be reduced to degree less than n with the irreducible polynomial. These components are called the basis and for a field over the binary field of two elements, the coefficients of the basis are simply zeros and ones. If the resulting n-tuple of coefficients is ordered corresponding to the sequence .alpha..sup.0,.alpha..sup.1, . . . .alpha..sup.n-1, then the field has been represented in polynomial order. If instead the coefficients are ordered to correspond to the sequence .alpha..sup.2.spsp.0, .alpha..sup.2.spsp.1, . . . , .alpha..sup.2.spsp.n-1 (when these powers are of normal basis for the finite field) then the representation is in normal basis order. However when in polynomial order we will denote the basis elements in terms of a polynomial in x. This representation has several advantages for hardware implementation and is more fully described in UK patent application GB2,176,325.
For implementation on a binary processor, the components are typically distributed across several processor words (which can be considered as a multi-word register), since a single processor word is not sufficient to hold all components if the length of the finite field is even moderately large. The length of these registers will exceed one hundred bits even for efficient elliptic curve crypto-systems. Smartcard systems are typically very memory poor (at least for RAM memory) and this invention stems from (but is not limited to) the work of the inventors to implement public key systems in such environments. The processors available in such systems are typically also not highly powered, so it is also of importance to develop efficient methods that can be useful in that environment.